package leetcode_600;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

/**
 *@author 周杨
 *LongestUncommonSubsequenceII_522 找出所有串中最大的非重复子序列
 *describe:用排序后的串 判断其是否在重复集合里 
 *2018年9月10日 上午10:55:04
 */
public class LongestUncommonSubsequenceII_522 {
	 /**
	 * describe:暴力解 搜索完所有空间 AC 58%
	 * 2018年9月10日 上午10:52:35
	 */
	public int findLUSlength1(String[] strs) {
	        int res=-1, n=strs.length;
	        for (int i=0; i<n; i++){
	            if (strs[i].length()<res) continue;
	            int j=-1;
	            while(++j<n) if (i!=j && isSubsequence(strs[i], strs[j])) break;
	            if (j==n) res=Math.max(res, strs[i].length());
	        }
	        return res;
	}
	
	
	 /**
	 * describe:a是否是b的子串
	 * 2018年9月10日 上午10:50:13
	 */
	public boolean isSubsequence(String a, String b){
	        int i=0, j=0;
	        while(i<a.length() && j<b.length()) if (a.charAt(i)==b.charAt(j++)) i++;
	        return i==a.length();
	    }
	
	
	 /**
	 * describe:排序后搜索 AC 30%
	 * 2018年9月10日 上午10:54:15
	 */
	public int findLUSlength(String[] strs) {
	        Arrays.sort(strs, new Comparator<String>() {
	            public int compare(String o1, String o2) {
	                return o2.length() - o1.length();
	            }
	        });
	        
	        Set<String> duplicates = getDuplicates(strs);//得到重复串
	        for(int i = 0; i < strs.length; i++) {
	            if(!duplicates.contains(strs[i])) {
	                if(i == 0) return strs[0].length();
	                for(int j = 0; j < i; j++) {
	                    if(isSubsequence(strs[j], strs[i])) break;
	                    if(j == i-1) return strs[i].length();
	                }
	            }
	        }
	        return -1;
	    }
	    

	    
	    private Set<String> getDuplicates(String[] strs) {
	        Set<String> set = new HashSet<String>();
	        Set<String> duplicates = new HashSet<String>();
	        for(String s : strs) {
	            if(set.contains(s)) duplicates.add(s);
	            set.add(s);
	        }
	        return duplicates;
	    }
}
